/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <queue>

using namespace std;

void BTreeIndex::ToString()
{
  cout << endl << "BTreeIndex ****************************" << endl;
  cout << "Tree Height: " << treeHeight << endl;
  cout << "Root PID: " << rootPid << endl;
  cout << "***************NODES****************" << endl;
  
  queue<PageId> myPids;
  queue<int> level;

  myPids.push(rootPid);
  level.push(1);


  while(!myPids.empty())
  {
    PageId pid = myPids.front();
    myPids.pop();
    int lev = level.front();
    level.pop();

    if(lev < treeHeight)
    {
      cout << (int)pid << ") NON LEAF NODE AT LEVEL " << lev << endl;
      BTNonLeafNode node;
      node.read(pid, pf);
      node.ToString();
      
      myPids.push(node.getFirst());
      level.push(lev+1);
      for(int i=0; i<node.getKeyCount(); i++)
      {
        myPids.push(node.getAt(i));
	level.push(lev+1);
      }
    }
    else
    {
      cout << (int)pid << ") LEAF NODE AT LEVEL " << lev << endl;
      BTLeafNode node;
      node.read(pid, pf);
      node.ToString();
    }
  }

}

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
  if(pf.open(indexname, mode) != 0)
    return -1;

  if(pf.endPid() > 0)
  {
    char buffer[PageFile::PAGE_SIZE];
    pf.read(0, buffer);

    int* treeHeightPtr = (int *)buffer;
    PageId* rootPidPtr = (PageId *)(buffer + sizeof(int));

    treeHeight = *treeHeightPtr;
    rootPid = *rootPidPtr;

    return 0;
  }
  
  rootPid = 1;
  treeHeight = 1;
  writeMetaDataToFile();

  BTLeafNode root;
  root.clear();
  root.setNextNodePtr(NULL);
  root.write(rootPid, pf);
  
  return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
  //cout << "Insert key " << key << ":" << endl;
  IndexCursor myCursor;
  locate(key, myCursor);

  //cout << "CURSOR: " << myCursor.pid << endl;

  BTLeafNode myLeaf;
  myLeaf.read(myCursor.pid, pf);

  //cout << "Tying to insert to page id " << myCursor.pid << endl;

  if(myLeaf.insert(key, rid) == 0)
  {
    //cout << "Inserted key " << key << " with no overflow." << endl;
    // Easy case, no leaf overflow
    myLeaf.write(myCursor.pid, pf);
    return 0;
  }

  // Leaf overflow, split leaf node
  BTLeafNode sib;
  sib.clear();
  PageId siblingPid = pf.endPid();
  int siblingKey;

  myLeaf.insertAndSplit(key, rid, sib, siblingKey);

  myLeaf.setNextNodePtr(siblingPid);
  sib.setNextNodePtr(NULL);
  myLeaf.write(myCursor.pid, pf);
  sib.write(siblingPid, pf);

  //cout << "Node full when trying to insert splitting." << endl;

  // Tree has only one level and we just split root node
  // Create new root node
  if(treeHeight == 1)
  {
    BTNonLeafNode newRoot;
    newRoot.initializeRoot(myCursor.pid, siblingKey, siblingPid);

    treeHeight++;
    rootPid = pf.endPid();
    newRoot.write(rootPid, pf);

    writeMetaDataToFile();

    //cout << "Split root node, making new root." << endl;

    return 0;
  }

  // Try to insert key for new sibling to parent node
  return insertOneLevelUp(siblingKey, siblingPid, treeHeight-1);
}

RC BTreeIndex::writeMetaDataToFile()
{
  char buffer[PageFile::PAGE_SIZE];
  int* treeHeightPtr = (int *)buffer;
  PageId* rootPidPtr = (PageId *)(buffer + sizeof(int));

  *treeHeightPtr = treeHeight;
  *rootPidPtr = rootPid;

  return pf.write(0, buffer);
}

RC BTreeIndex::insertOneLevelUp(int key, PageId pid, int level)
{
  //cout << "Trying to insert key " << key << " level up: " << level << endl;
  // Locate parent node at 'level' of tree
  int curLevel = 1;
  PageId curPid = rootPid;
  BTNonLeafNode curNode;

  while(curLevel < level)
  {
    curNode.read(curPid, pf);
    curNode.locateChildPtr(key, curPid);
    curLevel++;
  }

  curNode.read(curPid, pf);

  // Easy case, no overflow
  if(curNode.insert(key, pid) == 0)
  {
    curNode.write(curPid, pf);
    //cout << "Insert successfull, no overflow" << endl;
    return 0;
  }

  // Overflow, split node
  BTNonLeafNode sibling;
  PageId siblingPid = pf.endPid();
  int midKey;

  curNode.insertAndSplit(key, pid, sibling, midKey);

  curNode.write(curPid, pf);
  sibling.write(siblingPid, pf);

  //cout << "Node full when inserting key, splitting node" << endl;

  // Just split root node
  // Create new root node
  if(level == 1)
  {
    BTNonLeafNode newRoot;
    newRoot.initializeRoot(curPid, midKey, siblingPid);

    treeHeight++;
    rootPid = pf.endPid();
    newRoot.write(rootPid, pf);
    writeMetaDataToFile();
    //cout << "Split root, creating new root" << endl;
    return 0;
  }

  //cout << "Inserting new key further up" << endl;

  // Try to insert key for new sibling to parent node
  return insertOneLevelUp(midKey, siblingPid, level-1);
  
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
  int curLevel = 1;
  PageId curPid = rootPid;
  while(curLevel < treeHeight)
  {
    BTNonLeafNode curNode;
    curNode.read(curPid, pf);
    curNode.locateChildPtr(searchKey, curPid);
    curLevel++;
  }

  BTLeafNode leafNode;
  leafNode.read(curPid, pf);
  cursor.pid = curPid;
  leafNode.locate(searchKey, cursor.eid);

  return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
  BTLeafNode leafNode;
  leafNode.read(cursor.pid, pf);

  leafNode.readEntry(cursor.eid, key, rid);

  cursor.eid = cursor.eid+1;
  if(cursor.eid >= leafNode.getKeyCount())
  {
    cursor.eid = 0;
    cursor.pid = leafNode.getNextNodePtr();
  }

  return 0;
}
